⟸ Go Back ⟸

Exercise 4 (Homework 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE)

Classification IV: image of computable functions

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid |\mathrm{Im}(\varphi_p)|\geq 0\}
2. \{p \mid |\mathrm{Im}(\varphi_p)|\geq 10\} (solving this RACSO exercise might give some hints)
3. \{p \mid \mathrm{Im}(\varphi_p)\subseteq 2\mathbb N\}
4. \{p \mid \mathrm{Im}(\varphi_p)\supseteq 2\mathbb N\}
5. \{p \mid \exists y\ \mathrm{Im}(\varphi_p)\subseteq \mathrm{Im}(\varphi_y)\}
6. \{p \mid \exists y\ \mathrm{Im}(\varphi_p)\supseteq \mathrm{Im}(\varphi_y)\}
7. \{p \mid \mathrm{Im}(\varphi_p)\in \mathbf{R}\}
8. \{p \mid \mathrm{Im}(\varphi_p)\notin \mathbf{R}\}
9. \{p \mid \mathrm{Im}(\varphi_p)\in \mathbf{RE}\}
10. \{p \mid \mathrm{Im}(\varphi_p)\notin \mathbf{RE}\}
11. \{p \mid p\leq 100 \land \mathrm{Im}(\varphi_p)\in \mathbf{R}\}
12. \{p \mid p\leq 100 \land \mathrm{Im}(\varphi_p)\in \mathbf{RE}\}
13. \{p \mid |\mathrm{Im}(\varphi_p)| < |\mathrm{Dom}(\varphi_p)|< \infty\}
14. \{p \mid |\mathrm{Dom}(\varphi_p)| < |\mathrm{Im}(\varphi_p)|< \infty\}